#include<stdio.h>
#include<stdlib.h>
#define MaxSize 100
typedef struct
{
	int col[MaxSize];
	int top;
 } StackType;
void dispasolution(StackType St)
{
	static int count=0;
	printf("第%d个解：",++count);
	for(int i=1;i<=St.top;i++)
	{
		printf("(%d,%d)",i,St.col[i]);
	}
	printf("\n");
}
bool place(StackType St,int k,int j)
{
	int i=1;
	if(k==1) return true;
	while(i<=k-1)
	{
		if((St.col[i]==j) ||(abs(j-St.col[i]))==abs(i-k))
		{
			return false;
		}
		i++;
	}
	return true;
}
void queen(int n)
{
	int k;
	bool find;
	StackType St;
	St.top=0;
	St.top++;St.col[St.top]=0;
	while(St.top!=0)
	{
		k=St.top;
		find=false;
		for(int j=St.col[k]+1;j<=n;j++)
		{
			if(place(St,k,j))
			{
				St.col[St.top]=j;
				find=true;
				break;
			}
	}
		if(find)
		{
			if(k==n)
			{
				dispasolution(St);
			}
			else
			{
				St.top++;
				St.col[St.top]=0;
			}
		}	
		else{
			St.top--;
		}
}
int main()
{
	int n;
	printf("皇后问题(n<20) n=");
	scanf("%d",&n);
	if(n>20)
	{
		print("n值太大\n");
	}
	else{
		printf("%d皇后问题求解如下：\n",n);
		queen(n);
	}
	return 1;
}